package class202205.demo25.demo23.Map;

import javax.xml.soap.Node;
import java.util.*;

public class demo {
    //统计重复出现的次数

    //key是关键子  value是出现的次数
    public static Map<Integer,Integer> fun1(int[] array){
        Map<Integer,Integer> map = new HashMap<>();
        //判断array中的元素是否在  map当中，如果不在就是1，在就是原来基础加1
        for (int x :array) {
            if (map.get(x) == null){
                map.put(x,1);
            }else {
                int val = map.get(x);
                map.put(x,val+1);
            }
        }
        return map;
    }

    public static Set<Integer> func2(int[] array){
        HashSet<Integer> set = new HashSet<>();
        for (int x :array) {
            set.add(x);
        }
        return set;
    }

    public static int func3(int[] array){
        HashSet<Integer> set = new HashSet<>();
        for (int x :array) {
            if (set.contains(x)){
                return x;
            }
            set.add(x);
        }
        return -1;
    }

    public static void main4(String[] args) {
        int[] array = new int[10_0000];
        Random random = new Random();
        for (int i = 0; i <array.length; i++) {
            array[i] = random.nextInt(10000);

        }
        Map<Integer,Integer> map = fun1(array);
        System.out.println(map);
    }

    /**
     * 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
     * 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
     * 链接：https://leetcode.cn/problems/single-number
     * @param nums
     * @return
     */
    public int singleNumber(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int x : nums){
            if (set.contains(x)){
                set.remove(x);
            }else {
                set.add(x);
            }
        }
        for (int i = 0; i < nums.length; i++) {
             if (set.contains(nums[i])){
                 return nums[i];
             }
        }
        return -1;
    }

    /**
     * 给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
     * 构造这个链表的深拷贝。深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。
     * 新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，
     * 并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
     * 链接：https://leetcode.cn/problems/copy-list-with-random-pointer
     * @param head
     * @return
     */
    public Node copyRandomList(Node head) {
        Map<Node,Node> map = new HashMap<>();
        Node cur = head;
        //存到map
        while (cur!= null){
            Node node = new Node(cur.val);
            map.put(cur,node);
            cur=cur.next;
        }
        cur=head;
        while (cur!=null){
            map.get(cur).next=map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur=cur.next;
        }
        return map.get(head);
    }

    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    /**
     * 给你一个字符串 jewels代表石头中宝石的类型，另有一个字符串 stones 代表你拥有的石头。
     * stones中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。
     * 字母区分大小写，因此 "a" 和 "A" 是不同类型的石头。
     * 链接：https://leetcode.cn/problems/jewels-and-stones
     * @param jewels
     * @param stones
     * @return
     */
    public int numJewelsInStones(String jewels, String stones) {
        HashSet<Character> set = new HashSet<>();
        //放字符入set
        for (Character ch: jewels.toCharArray()) {
            set.add(ch);
        }
        //遍历stones  看宝石多少
        int count = 0;
        for (Character ch: stones.toCharArray()) {
            if (set.contains(ch)){
                count++;
            }
        }
        return count;
    }

    /**
     * 旧键盘上坏了几个键，于是在敲一段文字的时候，对应的字符就不会出现。现在给出应该输入的一段文字、以及实际被输入的文字，请你列出
     * 肯定坏掉的那些键。
     * https://www.nowcoder.com/questionTerminal/f88dafac00c8431fa363cd85a37c2d5e
     * @param args
     */
    public static void main(String[] args) {
        func3("7_This_is_a_test","_hs_s_a_es");
    }

    public static void func3(String strExce,String strActual){
        HashSet<Character> set = new HashSet<>();
        //变为大写  转为字符
        for (char ch:strActual.toUpperCase().toCharArray()) {
            set.add(ch);
        }
        HashSet<Character> broken= new HashSet<>();
        //broken  剔除重复
        for (char ch:strExce.toUpperCase().toCharArray()) {
            if (!set.contains(ch) && !broken.contains(ch)){
                System.out.print(ch);
                broken.add(ch);
            }
        }
    }
   /* public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNextLine()){
            String str1 = scanner.nextLine();
            String str2 = scanner.nextLine();
            func(str1,str2);
        }
    }*/

    /**
     * 给定一个单词列表words和一个整数 k ，返回前k个出现次数最多的单词。
     * 返回的答案应该按单词出现频率由高到低排序。
     * 如果不同的单词有相同出现频率， 按字典顺序 排序。
     * 链接：https://leetcode.cn/problems/top-k-frequent-words
     * @param words
     * @param k
     * @return
     */
    public List<String> topKFrequent(String[] words, int k) {
        HashMap<String, Integer> map = new HashMap<>();
        //1、统计每个单词出现次数 map
        for (String s : words) {
            if (map.get(s) == null) {
                map.put(s, 1);

            } else {
                int val = map.get(s);
                map.put(s, val + 1);

            }
        }


        //2、建立大小为K的小根堆
        PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                //加一个  频率相同  按字母顺序进行排序
                if (o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue() - o2.getValue();
            }
        });

        //3、遍历map

        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (minHeap.size() < k) {
                minHeap.offer(entry);
            } else {
                //k放好了  再次放入需要比较
                Map.Entry<String, Integer> top = minHeap.peek();
                //看频率  相同   比较单词大小  小的入
                if (top.getValue().compareTo(entry.getValue()) == 0) {
                    if (top.getKey().compareTo(entry.getKey()) > 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                } else {
                    //频率不同
                    if (top.getValue().compareTo(entry.getValue()) < 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }
        System.out.println(minHeap);
        List<String> ret = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            Map.Entry<String, Integer> top = minHeap.poll();
            ret.add(top.getKey());
        }
        Collections.reverse(ret);

        return ret;
    }
}
